package algorithm.leetcode.medium;


/*
 给定一个二叉树，原地将它展开为一个单链表。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/30
 */
public class Question114 {

    public static void main(String[] args) {

    }

    /**
     * 思路： 前序遍历
     * 1、将左子树插入到右子树的地方
     * 2、将原来的右子树接到左子树的最右边节点
     * 3、考虑新的右子树的根节点，一直重复上边的过程，直到新的右子树为 null
     */
    public void flatten(TreeNode root) {
        while (root != null) {
            // 如果左子树为空 直接考虑下个节点
            if (root.left != null) {
                TreeNode pre = root.left;
                // 找到左子树的最右子树
                while (pre.right != null) {
                    pre = pre.right;
                }
                // 将原来的右子树放到左子树的右子树下面
                pre.right = root.right;
                // 将左子树放入到之前的右子树
                root.right = root.left;
                // 当前的左子树就没有了
                root.left = null;
                // 考虑下个节点
            }
            root = root.right;
        }

    }


    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
